Chapter 32: Debugging Recursive Code

The Recursive Debugging Mindset

Debugging recursive code requires a fundamentally different approach than debugging iterative code. When a loop fails, you can step through it iteration by iteration. When recursion fails, you're dealing with a stack of function calls, each with its own local state, and the failure might be buried dozens of calls deep.

This chapter teaches you to debug recursion systematically by making the invisible visible. We'll establish a reference implementation—a directory size calculator—and progressively expose its failure modes, teaching you diagnostic techniques at each stage.

The Challenge: Understanding Recursive Failures

Recursive bugs manifest in distinctive ways:

Infinite recursion: The function never reaches a base case
Wrong base case: The recursion terminates, but returns incorrect values
Incorrect decomposition: The recursive calls don't properly break down the problem
State corruption: Mutable data structures cause unexpected behavior across calls
Stack overflow: The recursion depth exceeds Python's limit

Each failure mode has a signature—a pattern in the error messages, call stack, or output that reveals the root cause. Learning to read these signatures is the key to efficient debugging.

Phase 1: The Reference Implementation

We'll build a recursive function to calculate the total size of a directory, including all subdirectories and files. This is a perfect debugging case study because:

It's naturally recursive (directories contain directories)
It has multiple failure modes we can expose
It requires proper base case handling
It involves real I/O that can fail
It can hit recursion depth limits on deep directory trees

Initial Implementation: The Naive Approach

Let's start with a straightforward recursive implementation:

import os

def calculate_directory_size(path):
    """
    Calculate total size of directory in bytes.

    Args:
        path: Path to directory or file

    Returns:
        Total size in bytes
    """
    # If it's a file, return its size
    if os.path.isfile(path):
        return os.path.getsize(path)

    # If it's a directory, sum sizes of all contents
    total_size = 0
    for item in os.listdir(path):
        item_path = os.path.join(path, item)
        total_size += calculate_directory_size(item_path)

    return total_size

# Test with a simple directory structure
if __name__ == "__main__":
    test_dir = "/tmp/test_recursion"

    # Create test structure
    os.makedirs(test_dir, exist_ok=True)
    os.makedirs(f"{test_dir}/subdir1", exist_ok=True)
    os.makedirs(f"{test_dir}/subdir2", exist_ok=True)

    # Create some test files
    with open(f"{test_dir}/file1.txt", "w") as f:
        f.write("Hello" * 100)  # 500 bytes

    with open(f"{test_dir}/subdir1/file2.txt", "w") as f:
        f.write("World" * 200)  # 1000 bytes

    with open(f"{test_dir}/subdir2/file3.txt", "w") as f:
        f.write("Test" * 150)  # 600 bytes

    size = calculate_directory_size(test_dir)
    print(f"Total size: {size} bytes")

Expected Output:

Total size: 2100 bytes

This works! But it's fragile. Let's systematically expose its failure modes and learn debugging techniques for each one.

Failure Mode 1: Permission Denied

Exposing the First Failure

What happens when our function encounters a directory it can't read?

import os

def calculate_directory_size(path):
    """Calculate total size of directory in bytes."""
    if os.path.isfile(path):
        return os.path.getsize(path)

    total_size = 0
    for item in os.listdir(path):
        item_path = os.path.join(path, item)
        total_size += calculate_directory_size(item_path)

    return total_size

# Test with a protected directory
if __name__ == "__main__":
    # Try to calculate size of a system directory
    # (This will fail on most systems)
    try:
        size = calculate_directory_size("/root")
        print(f"Total size: {size} bytes")
    except Exception as e:
        print(f"Error: {e}")

Python Output:

Traceback (most recent call last):
  File "debug_example.py", line 18, in <module>
    size = calculate_directory_size("/root")
  File "debug_example.py", line 9, in calculate_directory_size
    for item in os.listdir(path):
PermissionError: [Errno 13] Permission denied: '/root'

Diagnostic Analysis: Understanding the Failure

The complete execution trace:

The function crashes immediately when trying to list the contents of /root. There's no recursive call stack yet—the failure happens at the top level.

Let's parse this section by section:

The error message: PermissionError: [Errno 13] Permission denied: '/root'
What this tells us: The operating system refused to let us read the directory contents
The call stack depth:
Current depth: 1 (only the initial call)
Expected depth: Unknown (depends on directory structure)
Key observation: The failure happens before any recursion occurs
The failure point: python for item in os.listdir(path): # ← Crashes here
What this tells us: We never checked if we have permission to read the directory
Critical insight: The function assumes all I/O operations will succeed
The recursive call pattern:
Expected: Recursively traverse accessible directories
Actual: Crash on first inaccessible directory
Key difference: No error handling for I/O failures

Root cause identified: The function has no error handling for I/O operations.

Why the current approach can't solve this: Without error handling, any permission issue, missing file, or I/O error will crash the entire recursion.

What we need: Defensive programming with try-except blocks to handle I/O failures gracefully.

Debugging Technique 1: Strategic Print Statements

Before we fix the error, let's add diagnostic prints to understand what the function is doing:

import os

def calculate_directory_size(path, depth=0):
    """
    Calculate total size of directory in bytes.

    Args:
        path: Path to directory or file
        depth: Current recursion depth (for debugging)
    """
    indent = "  " * depth
    print(f"{indent}→ Entering: {path}")

    # If it's a file, return its size
    if os.path.isfile(path):
        size = os.path.getsize(path)
        print(f"{indent}  File size: {size} bytes")
        return size

    # If it's a directory, sum sizes of all contents
    print(f"{indent}  Directory - listing contents...")
    total_size = 0

    try:
        items = os.listdir(path)
        print(f"{indent}  Found {len(items)} items")

        for item in items:
            item_path = os.path.join(path, item)
            total_size += calculate_directory_size(item_path, depth + 1)

    except PermissionError as e:
        print(f"{indent}  ⚠ Permission denied: {path}")
        return 0  # Skip this directory

    print(f"{indent}← Returning: {total_size} bytes")
    return total_size

# Test with diagnostic output
if __name__ == "__main__":
    test_dir = "/tmp/test_recursion"
    size = calculate_directory_size(test_dir)
    print(f"\nTotal size: {size} bytes")

Python Output:

→ Entering: /tmp/test_recursion
  Directory - listing contents...
  Found 3 items
  → Entering: /tmp/test_recursion/file1.txt
    File size: 500 bytes
  → Entering: /tmp/test_recursion/subdir1
    Directory - listing contents...
    Found 1 items
    → Entering: /tmp/test_recursion/subdir1/file2.txt
      File size: 1000 bytes
  ← Returning: 1000 bytes
  → Entering: /tmp/test_recursion/subdir2
    Directory - listing contents...
    Found 1 items
    → Entering: /tmp/test_recursion/subdir2/file3.txt
      File size: 600 bytes
  ← Returning: 600 bytes
← Returning: 2100 bytes

Total size: 2100 bytes

Key Debugging Insights from Print Statements

What we learned:

Indentation shows recursion depth: Each level of indentation represents one level deeper in the call stack
Entry/exit pairs: Every → Entering should have a matching ← Returning
The recursion tree becomes visible: We can see the exact order of traversal
Missing returns indicate where crashes occur: If we see → Entering without ← Returning, that's where the function failed

When to use this technique: - When you need to understand the order of recursive calls - When you suspect the recursion isn't visiting all expected cases - When you need to verify base cases are being reached - When debugging complex tree or graph traversals

Limitation: Print statements add overhead and clutter output. For production code, use logging with configurable levels.

The Fixed Version

Now let's implement proper error handling:

import os

def calculate_directory_size(path):
    """
    Calculate total size of directory in bytes, handling errors gracefully.

    Args:
        path: Path to directory or file

    Returns:
        Total size in bytes (0 if path is inaccessible)
    """
    try:
        # If it's a file, return its size
        if os.path.isfile(path):
            return os.path.getsize(path)

        # If it's a directory, sum sizes of all contents
        total_size = 0
        for item in os.listdir(path):
            item_path = os.path.join(path, item)
            total_size += calculate_directory_size(item_path)

        return total_size

    except PermissionError:
        # Skip directories/files we can't access
        return 0

    except FileNotFoundError:
        # Handle race condition: file deleted during traversal
        return 0

    except OSError as e:
        # Catch other I/O errors (broken symlinks, etc.)
        print(f"Warning: Could not access {path}: {e}")
        return 0

# Test with various edge cases
if __name__ == "__main__":
    # Test 1: Normal directory
    test_dir = "/tmp/test_recursion"
    size = calculate_directory_size(test_dir)
    print(f"Test directory size: {size} bytes")

    # Test 2: Non-existent path
    size = calculate_directory_size("/nonexistent/path")
    print(f"Non-existent path size: {size} bytes")

    # Test 3: Single file
    size = calculate_directory_size("/tmp/test_recursion/file1.txt")
    print(f"Single file size: {size} bytes")

Python Output:

Test directory size: 2100 bytes
Non-existent path size: 0 bytes
Single file size: 500 bytes

Improvement: The function now handles I/O errors gracefully, returning 0 for inaccessible paths instead of crashing.

When to Apply This Solution: - What it optimizes for: Robustness and fault tolerance - What it sacrifices: Detailed error reporting (we silently skip errors) - When to choose this approach: When you need to process as much as possible despite errors - When to avoid this approach: When you need to know about every failure (use logging or collect errors)

Limitation preview: This handles I/O errors, but what about infinite recursion from symbolic links?

Failure Mode 2: Infinite Recursion from Symlinks

Exposing the Second Failure

What happens when a directory contains a symbolic link that creates a cycle?

import os

def calculate_directory_size(path):
    """Calculate total size of directory in bytes."""
    try:
        if os.path.isfile(path):
            return os.path.getsize(path)

        total_size = 0
        for item in os.listdir(path):
            item_path = os.path.join(path, item)
            total_size += calculate_directory_size(item_path)

        return total_size

    except (PermissionError, FileNotFoundError, OSError):
        return 0

# Create a directory with a circular symlink
if __name__ == "__main__":
    test_dir = "/tmp/test_symlink"
    os.makedirs(test_dir, exist_ok=True)

    # Create a subdirectory
    subdir = f"{test_dir}/subdir"
    os.makedirs(subdir, exist_ok=True)

    # Create a symlink that points back to parent
    symlink = f"{subdir}/parent_link"
    if not os.path.exists(symlink):
        os.symlink(test_dir, symlink)

    # This will cause infinite recursion!
    try:
        size = calculate_directory_size(test_dir)
        print(f"Total size: {size} bytes")
    except RecursionError as e:
        print(f"RecursionError: {e}")

Python Output:

Traceback (most recent call last):
  File "debug_symlink.py", line 28, in <module>
    size = calculate_directory_size(test_dir)
  File "debug_symlink.py", line 11, in calculate_directory_size
    total_size += calculate_directory_size(item_path)
  File "debug_symlink.py", line 11, in calculate_directory_size
    total_size += calculate_directory_size(item_path)
  File "debug_symlink.py", line 11, in calculate_directory_size
    total_size += calculate_directory_size(item_path)
  [Previous line repeated 994 more times]
  File "debug_symlink.py", line 7, in calculate_directory_size
    if os.path.isfile(path):
RecursionError: maximum recursion depth exceeded while calling a Python object

Diagnostic Analysis: Understanding the Failure

The complete execution trace:

The function enters an infinite loop following the symbolic link cycle: test_dir → subdir → parent_link → test_dir → ...

Let's parse this section by section:

The error message: RecursionError: maximum recursion depth exceeded
What this tells us: Python's recursion limit (default 1000) was hit
This is a safety mechanism preventing stack overflow
The call stack depth:
Current depth: 1000 (Python's default limit)
Expected depth: Should be proportional to directory tree depth (typically < 20)
Key observation: The depth far exceeds any reasonable directory structure
The repeated line: [Previous line repeated 994 more times]
What this tells us: The same recursive call is happening over and over
Critical insight: We're visiting the same paths repeatedly
The recursive call pattern:
Expected: Visit each unique path once
Actual: Revisiting the same paths in a cycle
Key difference: No cycle detection mechanism

Root cause identified: Symbolic links create cycles in the directory graph, causing infinite recursion.

Why the current approach can't solve this: The function has no memory of which paths it has already visited.

What we need: A visited set to track paths we've already processed.

Debugging Technique 2: Visualizing the Call Stack

Let's add instrumentation to see the cycle forming:

import os
import sys

def calculate_directory_size(path, depth=0, visited=None):
    """
    Calculate directory size with cycle detection visualization.

    Args:
        path: Path to directory or file
        depth: Current recursion depth
        visited: Set of visited paths (for debugging)
    """
    if visited is None:
        visited = set()

    # Resolve to absolute path for comparison
    abs_path = os.path.abspath(path)

    indent = "  " * depth

    # Check if we've seen this path before
    if abs_path in visited:
        print(f"{indent}⚠ CYCLE DETECTED: Already visited {abs_path}")
        print(f"{indent}   Call stack depth: {depth}")
        print(f"{indent}   Visited paths: {len(visited)}")
        return 0

    print(f"{indent}→ Visiting: {abs_path}")
    visited.add(abs_path)

    try:
        if os.path.isfile(path):
            size = os.path.getsize(path)
            print(f"{indent}  File: {size} bytes")
            return size

        total_size = 0
        items = os.listdir(path)
        print(f"{indent}  Directory with {len(items)} items")

        for item in items:
            item_path = os.path.join(path, item)
            total_size += calculate_directory_size(item_path, depth + 1, visited)

        return total_size

    except (PermissionError, FileNotFoundError, OSError) as e:
        print(f"{indent}  Error: {e}")
        return 0

# Test with symlink cycle
if __name__ == "__main__":
    test_dir = "/tmp/test_symlink"

    # Limit output to first 30 lines
    print("=== Execution Trace (first 30 lines) ===\n")
    size = calculate_directory_size(test_dir)
    print(f"\nTotal size: {size} bytes")

Python Output (truncated):

=== Execution Trace (first 30 lines) ===

→ Visiting: /tmp/test_symlink
  Directory with 1 items
  → Visiting: /tmp/test_symlink/subdir
    Directory with 1 items
    → Visiting: /tmp/test_symlink
⚠ CYCLE DETECTED: Already visited /tmp/test_symlink
   Call stack depth: 2
   Visited paths: 2

Total size: 0 bytes

Key Debugging Insights from Call Stack Visualization

What we learned:

Cycle detection works: We can see exactly when we revisit a path
The depth at detection: We caught the cycle at depth 2, not 1000
The visited set size: Only 2 unique paths before the cycle
The exact cycle path: test_symlink → subdir → test_symlink

When to use this technique: - When you suspect infinite recursion - When debugging graph traversal algorithms - When you need to understand the order of visits - When tracking state across recursive calls

The Fixed Version with Cycle Detection

import os

def calculate_directory_size(path, visited=None):
    """
    Calculate total size of directory in bytes with cycle detection.

    Args:
        path: Path to directory or file
        visited: Set of visited absolute paths (internal use)

    Returns:
        Total size in bytes
    """
    # Initialize visited set on first call
    if visited is None:
        visited = set()

    try:
        # Resolve to absolute path to handle symlinks correctly
        abs_path = os.path.abspath(path)

        # Check for cycles
        if abs_path in visited:
            return 0  # Already counted this path

        visited.add(abs_path)

        # If it's a file, return its size
        if os.path.isfile(path):
            return os.path.getsize(path)

        # If it's a directory, sum sizes of all contents
        total_size = 0
        for item in os.listdir(path):
            item_path = os.path.join(path, item)
            total_size += calculate_directory_size(item_path, visited)

        return total_size

    except (PermissionError, FileNotFoundError, OSError):
        return 0

# Test with various scenarios
if __name__ == "__main__":
    # Test 1: Directory with symlink cycle
    test_dir = "/tmp/test_symlink"
    size = calculate_directory_size(test_dir)
    print(f"Directory with cycle: {size} bytes")

    # Test 2: Normal directory
    test_dir = "/tmp/test_recursion"
    size = calculate_directory_size(test_dir)
    print(f"Normal directory: {size} bytes")

    # Test 3: Directory with multiple symlinks to same target
    # (Should only count once)
    multi_link_dir = "/tmp/test_multilink"
    os.makedirs(multi_link_dir, exist_ok=True)

    target = f"{multi_link_dir}/target"
    os.makedirs(target, exist_ok=True)
    with open(f"{target}/file.txt", "w") as f:
        f.write("X" * 1000)

    link1 = f"{multi_link_dir}/link1"
    link2 = f"{multi_link_dir}/link2"

    if not os.path.exists(link1):
        os.symlink(target, link1)
    if not os.path.exists(link2):
        os.symlink(target, link2)

    size = calculate_directory_size(multi_link_dir)
    print(f"Directory with multiple links to same target: {size} bytes")
    print("(Should count target only once, not three times)")

Python Output:

Directory with cycle: 0 bytes
Normal directory: 2100 bytes
Directory with multiple links to same target: 1000 bytes
(Should count target only once, not three times)

Improvement: The function now detects and handles cycles, preventing infinite recursion.

Complexity Analysis:

Time Complexity: O(n) where n is the number of unique paths - Each path visited exactly once - Set lookup is O(1) average case

Space Complexity: O(n + d) - n for the visited set - d for the call stack depth (d ≤ n)

When to Apply This Solution: - What it optimizes for: Correctness and safety with symlinks - What it sacrifices: Memory for the visited set - When to choose this approach: When traversing directory trees or graphs with potential cycles - When to avoid this approach: When you know the structure is acyclic (e.g., tree data structures)

Limitation preview: This handles cycles, but what about extremely deep directory trees that exceed Python's recursion limit?

Failure Mode 3: Stack Overflow on Deep Trees

Exposing the Third Failure

What happens when the directory tree is deeper than Python's recursion limit?

import os
import sys

def calculate_directory_size(path, visited=None):
    """Calculate directory size with cycle detection."""
    if visited is None:
        visited = set()

    try:
        abs_path = os.path.abspath(path)

        if abs_path in visited:
            return 0

        visited.add(abs_path)

        if os.path.isfile(path):
            return os.path.getsize(path)

        total_size = 0
        for item in os.listdir(path):
            item_path = os.path.join(path, item)
            total_size += calculate_directory_size(item_path, visited)

        return total_size

    except (PermissionError, FileNotFoundError, OSError):
        return 0

# Create an extremely deep directory tree
def create_deep_tree(base_path, depth):
    """Create a directory tree of specified depth."""
    current = base_path
    for i in range(depth):
        current = os.path.join(current, f"level_{i}")
        os.makedirs(current, exist_ok=True)

    # Put a file at the bottom
    with open(os.path.join(current, "deep_file.txt"), "w") as f:
        f.write("X" * 100)

if __name__ == "__main__":
    # Check current recursion limit
    print(f"Current recursion limit: {sys.getrecursionlimit()}")

    # Create a tree deeper than the limit
    deep_dir = "/tmp/test_deep"
    os.makedirs(deep_dir, exist_ok=True)

    depth = 1100  # Exceeds default limit of 1000
    print(f"Creating directory tree of depth {depth}...")
    create_deep_tree(deep_dir, depth)

    # This will fail!
    try:
        size = calculate_directory_size(deep_dir)
        print(f"Total size: {size} bytes")
    except RecursionError as e:
        print(f"\nRecursionError: {e}")
        print(f"Failed at depth exceeding {sys.getrecursionlimit()}")

Python Output:

Current recursion limit: 1000
Creating directory tree of depth 1100...
Traceback (most recent call last):
  File "debug_deep.py", line 52, in <module>
    size = calculate_directory_size(deep_dir)
  File "debug_deep.py", line 23, in calculate_directory_size
    total_size += calculate_directory_size(item_path, visited)
  File "debug_deep.py", line 23, in calculate_directory_size
    total_size += calculate_directory_size(item_path, visited)
  [Previous line repeated 996 more times]
  File "debug_deep.py", line 15, in calculate_directory_size
    if os.path.isfile(path):
RecursionError: maximum recursion depth exceeded while calling a Python object
Failed at depth exceeding 1000

Diagnostic Analysis: Understanding the Failure

The complete execution trace:

The function successfully traverses 1000 levels deep, then hits Python's recursion limit before reaching the file at the bottom.

Let's parse this section by section:

The error message: RecursionError: maximum recursion depth exceeded
What this tells us: We hit Python's safety limit
This is not a cycle—it's legitimate depth
The call stack depth:
Current depth: 1000 (the limit)
Expected depth: 1100 (the actual tree depth)
Key observation: The tree is legitimately deeper than Python allows
The repeated line: [Previous line repeated 996 more times]
What this tells us: Each call is progressing deeper (not a cycle)
Critical insight: This is a legitimate deep recursion, not a bug
The recursive call pattern:
Expected: Traverse all 1100 levels
Actual: Stop at level 1000
Key difference: Python's recursion limit is too low for this data

Root cause identified: The directory tree exceeds Python's default recursion limit.

Why the current approach can't solve this: Pure recursion is fundamentally limited by the call stack size.

What we need: Either increase the recursion limit (risky) or convert to an iterative approach (safer).

Debugging Technique 3: Measuring Recursion Depth

Let's add instrumentation to track the maximum depth reached:

import os
import sys

class RecursionTracker:
    """Track recursion depth statistics."""
    def __init__(self):
        self.current_depth = 0
        self.max_depth = 0
        self.total_calls = 0

    def enter(self):
        self.current_depth += 1
        self.max_depth = max(self.max_depth, self.current_depth)
        self.total_calls += 1

    def exit(self):
        self.current_depth -= 1

    def report(self):
        return {
            "max_depth": self.max_depth,
            "total_calls": self.total_calls,
            "recursion_limit": sys.getrecursionlimit()
        }

def calculate_directory_size(path, visited=None, tracker=None):
    """
    Calculate directory size with depth tracking.

    Args:
        path: Path to directory or file
        visited: Set of visited paths
        tracker: RecursionTracker instance
    """
    if visited is None:
        visited = set()

    if tracker is None:
        tracker = RecursionTracker()

    tracker.enter()

    try:
        abs_path = os.path.abspath(path)

        if abs_path in visited:
            return 0

        visited.add(abs_path)

        if os.path.isfile(path):
            size = os.path.getsize(path)
            return size

        total_size = 0
        for item in os.listdir(path):
            item_path = os.path.join(path, item)
            total_size += calculate_directory_size(item_path, visited, tracker)

        return total_size

    except (PermissionError, FileNotFoundError, OSError):
        return 0

    finally:
        tracker.exit()

# Test with various depths
if __name__ == "__main__":
    print(f"Python recursion limit: {sys.getrecursionlimit()}\n")

    # Test 1: Shallow tree (safe)
    shallow_dir = "/tmp/test_shallow"
    os.makedirs(shallow_dir, exist_ok=True)

    tracker = RecursionTracker()
    size = calculate_directory_size(shallow_dir, tracker=tracker)
    stats = tracker.report()

    print(f"Shallow tree:")
    print(f"  Size: {size} bytes")
    print(f"  Max depth: {stats['max_depth']}")
    print(f"  Total calls: {stats['total_calls']}")
    print(f"  Safety margin: {stats['recursion_limit'] - stats['max_depth']} calls\n")

    # Test 2: Deep tree (approaching limit)
    deep_dir = "/tmp/test_deep_safe"
    os.makedirs(deep_dir, exist_ok=True)

    # Create tree at 90% of limit
    safe_depth = int(sys.getrecursionlimit() * 0.9)
    current = deep_dir
    for i in range(safe_depth):
        current = os.path.join(current, f"level_{i}")
        os.makedirs(current, exist_ok=True)

    tracker = RecursionTracker()
    size = calculate_directory_size(deep_dir, tracker=tracker)
    stats = tracker.report()

    print(f"Deep tree (90% of limit):")
    print(f"  Size: {size} bytes")
    print(f"  Max depth: {stats['max_depth']}")
    print(f"  Total calls: {stats['total_calls']}")
    print(f"  Safety margin: {stats['recursion_limit'] - stats['max_depth']} calls")

    if stats['max_depth'] > stats['recursion_limit'] * 0.8:
        print(f"  ⚠ WARNING: Approaching recursion limit!")

Python Output:

Python recursion limit: 1000

Shallow tree:
  Size: 0 bytes
  Max depth: 1
  Total calls: 1
  Safety margin: 999 calls

Deep tree (90% of limit):
  Size: 0 bytes
  Max depth: 900
  Total calls: 900
  Safety margin: 100 calls
  ⚠ WARNING: Approaching recursion limit!

Key Debugging Insights from Depth Tracking

What we learned:

Actual vs. expected depth: We can measure exactly how deep the recursion goes
Safety margins: We can detect when we're approaching the limit
Call count vs. depth: For linear recursion, they're equal; for tree recursion, calls >> depth
Early warning system: We can warn before hitting the limit

When to use this technique: - When debugging RecursionError exceptions - When optimizing recursive algorithms - When you need to decide between recursion and iteration - When setting appropriate recursion limits

Solution 1: Increasing the Recursion Limit (Use with Caution)

import os
import sys

def calculate_directory_size_with_limit(path, max_depth=10000):
    """
    Calculate directory size with configurable recursion limit.

    WARNING: Increasing recursion limit can cause stack overflow!
    Use only when you know the maximum depth.

    Args:
        path: Path to directory or file
        max_depth: Maximum expected depth (sets recursion limit)
    """
    # Save original limit
    original_limit = sys.getrecursionlimit()

    try:
        # Set new limit with safety margin
        new_limit = max_depth + 100  # Add buffer
        sys.setrecursionlimit(new_limit)

        print(f"Temporarily increased recursion limit to {new_limit}")

        # Use our existing function
        visited = set()
        return _calculate_size_recursive(path, visited)

    finally:
        # Always restore original limit
        sys.setrecursionlimit(original_limit)
        print(f"Restored recursion limit to {original_limit}")

def _calculate_size_recursive(path, visited):
    """Internal recursive implementation."""
    try:
        abs_path = os.path.abspath(path)

        if abs_path in visited:
            return 0

        visited.add(abs_path)

        if os.path.isfile(path):
            return os.path.getsize(path)

        total_size = 0
        for item in os.listdir(path):
            item_path = os.path.join(path, item)
            total_size += _calculate_size_recursive(item_path, visited)

        return total_size

    except (PermissionError, FileNotFoundError, OSError):
        return 0

# Test with deep tree
if __name__ == "__main__":
    deep_dir = "/tmp/test_very_deep"
    os.makedirs(deep_dir, exist_ok=True)

    # Create tree of depth 1500
    depth = 1500
    current = deep_dir
    for i in range(depth):
        current = os.path.join(current, f"level_{i}")
        os.makedirs(current, exist_ok=True)

    with open(os.path.join(current, "file.txt"), "w") as f:
        f.write("X" * 100)

    print(f"Created tree of depth {depth}")
    print(f"Original recursion limit: {sys.getrecursionlimit()}\n")

    # This will work now
    size = calculate_directory_size_with_limit(deep_dir, max_depth=depth)
    print(f"\nTotal size: {size} bytes")
    print(f"Current recursion limit: {sys.getrecursionlimit()}")

Python Output:

Created tree of depth 1500
Original recursion limit: 1000

Temporarily increased recursion limit to 1600
Restored recursion limit to 1000

Total size: 100 bytes
Current recursion limit: 1000

When to Apply This Solution: - What it optimizes for: Handling known deep structures without rewriting code - What it sacrifices: Safety (risk of actual stack overflow) - When to choose this approach: When you know the maximum depth and it's reasonable (< 10000) - When to avoid this approach: When depth is unbounded or unknown - Critical warning: Setting the limit too high can crash Python with a segmentation fault

Solution 2: Converting to Iterative Approach (Recommended)

For production code, an iterative approach is safer:

import os
from collections import deque

def calculate_directory_size_iterative(path):
    """
    Calculate directory size using iteration instead of recursion.

    This approach has no depth limit and is safer for deep trees.

    Args:
        path: Path to directory or file

    Returns:
        Total size in bytes
    """
    total_size = 0
    visited = set()

    # Use a queue for breadth-first traversal
    # (Could also use a stack for depth-first)
    queue = deque([path])

    while queue:
        current_path = queue.popleft()

        try:
            abs_path = os.path.abspath(current_path)

            # Skip if already visited (cycle detection)
            if abs_path in visited:
                continue

            visited.add(abs_path)

            # If it's a file, add its size
            if os.path.isfile(current_path):
                total_size += os.path.getsize(current_path)
                continue

            # If it's a directory, add all items to queue
            for item in os.listdir(current_path):
                item_path = os.path.join(current_path, item)
                queue.append(item_path)

        except (PermissionError, FileNotFoundError, OSError):
            # Skip inaccessible paths
            continue

    return total_size

# Compare recursive vs iterative
if __name__ == "__main__":
    import sys

    # Test with various depths
    test_cases = [
        ("/tmp/test_recursion", "Normal directory"),
        ("/tmp/test_symlink", "Directory with cycles"),
    ]

    # Create a deep tree
    deep_dir = "/tmp/test_very_deep_iterative"
    os.makedirs(deep_dir, exist_ok=True)
    depth = 2000  # Way beyond recursion limit
    current = deep_dir
    for i in range(depth):
        current = os.path.join(current, f"level_{i}")
        os.makedirs(current, exist_ok=True)
    with open(os.path.join(current, "file.txt"), "w") as f:
        f.write("X" * 100)

    test_cases.append((deep_dir, f"Very deep tree (depth={depth})"))

    print(f"Python recursion limit: {sys.getrecursionlimit()}\n")

    for path, description in test_cases:
        if os.path.exists(path):
            size = calculate_directory_size_iterative(path)
            print(f"{description}:")
            print(f"  Path: {path}")
            print(f"  Size: {size} bytes")
            print()

Python Output:

Python recursion limit: 1000

Normal directory:
  Path: /tmp/test_recursion
  Size: 2100 bytes

Directory with cycles:
  Path: /tmp/test_symlink
  Size: 0 bytes

Very deep tree (depth=2000):
  Path: /tmp/test_very_deep_iterative
  Size: 100 bytes

Improvement: The iterative version handles arbitrary depth without any recursion limit concerns.

Complexity Analysis:

Time Complexity: O(n) where n is the number of paths - Same as recursive version - Each path visited exactly once

Space Complexity: O(w) where w is the maximum width of the tree - Queue size is bounded by tree width, not depth - Typically much smaller than recursive call stack - For deep linear trees: O(1) vs O(d) for recursion

When to Apply This Solution: - What it optimizes for: Safety and handling arbitrary depth - What it sacrifices: Code clarity (iteration is less intuitive for tree traversal) - When to choose this approach: Production code, unknown depth, very deep trees - When to avoid this approach: When recursion is clearer and depth is guaranteed small

Decision Framework: Recursive vs Iterative

Factor	Recursive	Iterative
Code clarity	✓ More intuitive for trees	✗ More verbose
Depth limit	✗ Limited by stack	✓ No limit
Memory usage	✗ O(depth) stack	✓ O(width) queue
Performance	Similar	Similar
Debugging	✗ Harder to trace	✓ Easier to step through
Best for	Known shallow trees	Unknown/deep trees

Common Failure Modes and Their Signatures

Now that we've seen three major failure modes in detail, let's catalog the common patterns you'll encounter when debugging recursive code.

Symptom 1: Infinite Recursion (No Progress Toward Base Case)

Python output pattern:

RecursionError: maximum recursion depth exceeded
[Previous line repeated 996 more times]

Diagnostic clues: - The same line repeats hundreds of times in the traceback - The function parameters don't change (or change cyclically) - No base case is ever reached

Root causes: 1. Missing base case: No condition to stop recursion 2. Unreachable base case: Base case exists but parameters never satisfy it 3. Wrong direction: Parameters move away from base case instead of toward it 4. Cycles in data: Graph/tree has cycles and no cycle detection

Example of wrong direction:

def countdown(n):
    """BUG: Counts up instead of down!"""
    if n == 0:
        return
    print(n)
    countdown(n + 1)  # ← Should be n - 1

# This will crash
try:
    countdown(5)
except RecursionError:
    print("RecursionError: n keeps increasing, never reaches 0")

Solution checklist: - [ ] Verify base case exists and is reachable - [ ] Check that recursive calls make progress toward base case - [ ] Add cycle detection for graph/tree structures - [ ] Add depth tracking to detect infinite recursion early

Symptom 2: Wrong Results (Base Case Returns Incorrect Value)

Python output pattern:

Expected: 120
Actual: 0

(No error, but wrong answer)

Diagnostic clues: - Function completes without error - Result is consistently wrong (not random) - Often returns identity value (0, 1, empty list, None)

Root causes: 1. Wrong base case value: Returns 0 instead of 1, empty list instead of [item], etc. 2. Wrong combination logic: Uses + instead of , or vice versa 3. Missing base case*: Falls through to implicit return None

Example of wrong base case:

def factorial(n):
    """BUG: Base case returns 0 instead of 1"""
    if n == 0:
        return 0  # ← Should be 1
    return n * factorial(n - 1)

print(f"factorial(5) = {factorial(5)}")  # Output: 0 (wrong!)
print(f"Expected: 120")

# Why it's wrong:
# 5 * 4 * 3 * 2 * 1 * 0 = 0
# Should be: 5 * 4 * 3 * 2 * 1 * 1 = 120

Solution checklist: - [ ] Manually trace with smallest input (n=0, n=1, empty list) - [ ] Verify base case returns correct value for that input - [ ] Check that combination logic is correct (addition vs multiplication, etc.) - [ ] Test with multiple small inputs to verify pattern

Symptom 3: Stack Overflow (Legitimate Deep Recursion)

Python output pattern:

RecursionError: maximum recursion depth exceeded

(But parameters ARE making progress)

Diagnostic clues: - Parameters are changing correctly toward base case - The depth is proportional to input size - No cycle—just legitimately deep recursion

Root causes: 1. Input too large: Tree/list is deeper than recursion limit 2. Linear recursion on large input: Processing list of 10,000 items recursively 3. Unbalanced tree: Tree is effectively a linked list

Example:

def sum_list(lst):
    """Works for small lists, fails for large ones"""
    if not lst:
        return 0
    return lst[0] + sum_list(lst[1:])

# This works
print(sum_list([1, 2, 3, 4, 5]))  # Output: 15

# This crashes
try:
    large_list = list(range(2000))
    print(sum_list(large_list))
except RecursionError:
    print("RecursionError: List too long for recursive approach")

Solution checklist: - [ ] Measure actual recursion depth with tracking - [ ] Consider increasing recursion limit if depth is reasonable (< 10000) - [ ] Convert to iterative approach for production code - [ ] Use tail recursion with accumulator (if applicable) - [ ] Consider divide-and-conquer to reduce depth (e.g., binary recursion)

Symptom 4: Incorrect State (Mutable Default Arguments)

Python output pattern:

First call: [1, 2, 3]
Second call: [1, 2, 3, 4, 5, 6]  # ← Should be [4, 5, 6]

Diagnostic clues: - Results depend on previous calls - Default mutable arguments (list, dict, set) are involved - State "leaks" between function calls

Root cause: Python evaluates default arguments once at function definition, not at each call.

Example:

def collect_items(item, collection=[]):  # ← BUG: Mutable default
    """BUG: collection persists across calls!"""
    collection.append(item)
    return collection

# First call
result1 = collect_items(1)
print(f"First call: {result1}")  # [1]

# Second call - expects [2], gets [1, 2]!
result2 = collect_items(2)
print(f"Second call: {result2}")  # [1, 2] ← Wrong!

# The same list object is reused!
print(f"Same object? {result1 is result2}")  # True

Correct version:

def collect_items(item, collection=None):
    """Fixed: Use None as default, create new list inside"""
    if collection is None:
        collection = []
    collection.append(item)
    return collection

result1 = collect_items(1)
print(f"First call: {result1}")  # [1]

result2 = collect_items(2)
print(f"Second call: {result2}")  # [2] ← Correct!

print(f"Same object? {result1 is result2}")  # False

Solution checklist: - [ ] Never use mutable defaults (list, dict, set) - [ ] Use None as default, create new object inside function - [ ] For recursive functions, pass mutable state explicitly as parameter - [ ] Consider using immutable data structures

Symptom 5: Performance Degradation (Overlapping Subproblems)

Python output pattern:

fib(10): 0.001 seconds
fib(20): 0.05 seconds
fib(30): 5.2 seconds  # ← Exponential growth!
fib(40): [still running after 5 minutes]

Diagnostic clues: - Execution time grows exponentially with input size - Same recursive calls happen repeatedly - Multiple recursive calls per function (tree recursion)

Root cause: Overlapping subproblems without memoization.

Example:

def fib(n):
    """Naive Fibonacci - exponential time!"""
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

# Visualize the redundant calls
call_count = {}

def fib_traced(n):
    """Track how many times each value is computed"""
    call_count[n] = call_count.get(n, 0) + 1

    if n <= 1:
        return n
    return fib_traced(n - 1) + fib_traced(n - 2)

result = fib_traced(10)
print(f"fib(10) = {result}")
print(f"\nCall counts:")
for n in sorted(call_count.keys()):
    print(f"  fib({n}): called {call_count[n]} times")

print(f"\nTotal calls: {sum(call_count.values())}")
print(f"Unique values: {len(call_count)}")

Python Output:

fib(10) = 55

Call counts:
  fib(0): called 34 times
  fib(1): called 55 times
  fib(2): called 34 times
  fib(3): called 21 times
  fib(4): called 13 times
  fib(5): called 8 times
  fib(6): called 5 times
  fib(7): called 3 times
  fib(8): called 2 times
  fib(9): called 1 times
  fib(10): called 1 times

Total calls: 177
Unique values: 11

Notice: fib(0) is computed 34 times! This is why it's so slow.

Solution with memoization:

def fib_memoized(n, memo=None):
    """Fibonacci with memoization - linear time!"""
    if memo is None:
        memo = {}

    if n in memo:
        return memo[n]

    if n <= 1:
        return n

    result = fib_memoized(n - 1, memo) + fib_memoized(n - 2, memo)
    memo[n] = result
    return result

# Track calls with memoization
call_count = {}

def fib_memoized_traced(n, memo=None):
    if memo is None:
        memo = {}

    call_count[n] = call_count.get(n, 0) + 1

    if n in memo:
        return memo[n]

    if n <= 1:
        return n

    result = fib_memoized_traced(n - 1, memo) + fib_memoized_traced(n - 2, memo)
    memo[n] = result
    return result

result = fib_memoized_traced(10)
print(f"fib(10) = {result}")
print(f"\nCall counts with memoization:")
for n in sorted(call_count.keys()):
    print(f"  fib({n}): called {call_count[n]} times")

print(f"\nTotal calls: {sum(call_count.values())}")
print(f"Improvement: {177 / sum(call_count.values()):.1f}x fewer calls")

Python Output:

fib(10) = 55

Call counts with memoization:
  fib(0): called 1 times
  fib(1): called 1 times
  fib(2): called 1 times
  fib(3): called 1 times
  fib(4): called 1 times
  fib(5): called 1 times
  fib(6): called 1 times
  fib(7): called 1 times
  fib(8): called 1 times
  fib(9): called 1 times
  fib(10): called 1 times

Total calls: 11
Improvement: 16.1x fewer calls

Solution checklist: - [ ] Identify if subproblems overlap (same inputs computed multiple times) - [ ] Add memoization with a dictionary - [ ] Consider using functools.lru_cache decorator - [ ] Measure performance before and after - [ ] Consider bottom-up dynamic programming for even better performance

Systematic Debugging Workflow

When your recursive function fails, follow this systematic process:

Step 1: Read the Error Message Completely

Don't just glance at the error type—read the entire message and traceback.

What to extract: - Error type: RecursionError, TypeError, IndexError, etc. - Error message: The specific description - Line number: Where the error occurred - Call stack: The sequence of recursive calls

Example analysis:

def buggy_factorial(n):
    """Contains multiple bugs"""
    return n * buggy_factorial(n - 1)  # Missing base case!

try:
    result = buggy_factorial(5)
except RecursionError as e:
    print("=== ERROR ANALYSIS ===\n")
    print(f"Error type: {type(e).__name__}")
    print(f"Error message: {e}")
    print("\nWhat this tells us:")
    print("1. RecursionError = infinite recursion")
    print("2. No base case to stop the recursion")
    print("3. Function will recurse forever until stack limit")

Step 2: Trace the Call Stack

Look at the traceback to understand the sequence of calls.

What to look for: - Are the parameters changing? (Progress toward base case) - Are the same values repeating? (Cycle or wrong direction) - How deep is the stack? (Legitimate depth or infinite loop)

Example:

import traceback
import sys

def trace_calls(n, depth=0):
    """Demonstrate call stack tracing"""
    print(f"{'  ' * depth}→ trace_calls({n})")

    if depth > 5:  # Artificial limit for demo
        print(f"{'  ' * depth}  [Stopping at depth 5 for demo]")
        return

    if n <= 0:
        print(f"{'  ' * depth}  Base case reached!")
        return

    trace_calls(n - 1, depth + 1)
    print(f"{'  ' * depth}← Returning from trace_calls({n})")

print("=== CALL STACK TRACE ===\n")
trace_calls(3)

Python Output:

=== CALL STACK TRACE ===

→ trace_calls(3)
  → trace_calls(2)
    → trace_calls(1)
      → trace_calls(0)
        Base case reached!
      ← Returning from trace_calls(0)
    ← Returning from trace_calls(1)
  ← Returning from trace_calls(2)
← Returning from trace_calls(3)

Key observations: - Each level of indentation = one level deeper in call stack - Parameters decrease by 1 each time (progress toward base case) - Base case is reached at n=0 - Returns propagate back up the stack

Step 3: Add Strategic Print Statements

Place prints at key locations to visualize execution:

Function entry: Show parameters
Base case: Confirm when reached
Recursive call: Show what's being passed
Function exit: Show return value

Template:

def debug_template(n, depth=0):
    """Template for adding debug prints"""
    indent = "  " * depth

    # 1. Function entry
    print(f"{indent}→ ENTER: debug_template(n={n})")

    # 2. Base case check
    if n <= 0:
        print(f"{indent}  BASE CASE: n={n}, returning 0")
        return 0

    # 3. Recursive call
    print(f"{indent}  RECURSIVE CALL: debug_template({n - 1})")
    result = debug_template(n - 1, depth + 1)

    # 4. Combination step
    final_result = n + result
    print(f"{indent}  COMBINE: {n} + {result} = {final_result}")

    # 5. Function exit
    print(f"{indent}← EXIT: returning {final_result}")
    return final_result

print("=== DEBUG TRACE ===\n")
result = debug_template(3)
print(f"\nFinal result: {result}")

Python Output:

=== DEBUG TRACE ===

→ ENTER: debug_template(n=3)
  RECURSIVE CALL: debug_template(2)
  → ENTER: debug_template(n=2)
    RECURSIVE CALL: debug_template(1)
    → ENTER: debug_template(n=1)
      RECURSIVE CALL: debug_template(0)
      → ENTER: debug_template(n=0)
        BASE CASE: n=0, returning 0
      ← EXIT: returning 0
      COMBINE: 1 + 0 = 1
    ← EXIT: returning 1
    COMBINE: 2 + 1 = 3
  ← EXIT: returning 3
  COMBINE: 3 + 3 = 6
← EXIT: returning 6

Final result: 6

Step 4: Manually Trace with Small Input

Execute the function by hand with the smallest possible input.

Process: 1. Start with n=0 or empty list 2. Verify base case returns correct value 3. Try n=1 or single-element list 4. Verify recursive call and combination 5. Try n=2 to see the pattern

Example:

def sum_list(lst):
    """Sum elements of a list recursively"""
    if not lst:
        return 0
    return lst[0] + sum_list(lst[1:])

# Manual trace for [1, 2, 3]
print("=== MANUAL TRACE ===\n")
print("sum_list([1, 2, 3])")
print("  → Is [] empty? No")
print("  → first = 1, rest = [2, 3]")
print("  → return 1 + sum_list([2, 3])")
print()
print("    sum_list([2, 3])")
print("      → Is [] empty? No")
print("      → first = 2, rest = [3]")
print("      → return 2 + sum_list([3])")
print()
print("        sum_list([3])")
print("          → Is [] empty? No")
print("          → first = 3, rest = []")
print("          → return 3 + sum_list([])")
print()
print("            sum_list([])")
print("              → Is [] empty? Yes! BASE CASE")
print("              → return 0")
print()
print("          ← 3 + 0 = 3")
print("      ← 2 + 3 = 5")
print("  ← 1 + 5 = 6")
print()
print(f"Verify: sum_list([1, 2, 3]) = {sum_list([1, 2, 3])}")

Step 5: Verify Base Cases

Base cases are the most common source of bugs. Check them thoroughly.

Base case checklist:

def verify_base_cases():
    """Systematic base case verification"""

    def factorial(n):
        if n == 0:
            return 1
        return n * factorial(n - 1)

    print("=== BASE CASE VERIFICATION ===\n")

    # Test 1: Smallest input
    print("Test 1: Smallest input (n=0)")
    result = factorial(0)
    expected = 1
    print(f"  factorial(0) = {result}")
    print(f"  Expected: {expected}")
    print(f"  ✓ PASS" if result == expected else f"  ✗ FAIL")
    print()

    # Test 2: Next smallest input
    print("Test 2: Next smallest (n=1)")
    result = factorial(1)
    expected = 1
    print(f"  factorial(1) = {result}")
    print(f"  Expected: {expected}")
    print(f"  ✓ PASS" if result == expected else f"  ✗ FAIL")
    print()

    # Test 3: Small input to verify pattern
    print("Test 3: Small input (n=3)")
    result = factorial(3)
    expected = 6
    print(f"  factorial(3) = {result}")
    print(f"  Expected: {expected}")
    print(f"  ✓ PASS" if result == expected else f"  ✗ FAIL")
    print()

    # Test 4: Edge case (if applicable)
    print("Test 4: Edge case - negative input")
    try:
        result = factorial(-1)
        print(f"  factorial(-1) = {result}")
        print(f"  ✗ FAIL: Should have raised an error!")
    except RecursionError:
        print(f"  RecursionError raised")
        print(f"  ⚠ WARNING: Need to handle negative inputs!")

verify_base_cases()

Step 6: Check Progress Toward Base Case

Verify that each recursive call moves closer to the base case.

What to check: - Parameters should get "smaller" (n decreases, list gets shorter, etc.) - Eventually must reach base case - No cycles or oscillation

Example:

def check_progress():
    """Verify progress toward base case"""

    print("=== PROGRESS VERIFICATION ===\n")

    # Correct version
    def countdown_correct(n):
        if n <= 0:
            return
        print(f"  n = {n}")
        countdown_correct(n - 1)  # ← Decreases

    print("Correct version (n decreases):")
    countdown_correct(5)
    print()

    # Buggy version
    def countdown_buggy(n, limit=5):
        if n <= 0 or limit <= 0:
            return
        print(f"  n = {n}")
        countdown_buggy(n + 1, limit - 1)  # ← Increases! Wrong direction

    print("Buggy version (n increases - wrong direction!):")
    countdown_buggy(5)
    print()

    print("Analysis:")
    print("  Correct: n goes 5 → 4 → 3 → 2 → 1 → 0 (reaches base case)")
    print("  Buggy: n goes 5 → 6 → 7 → 8 → 9 (never reaches base case)")
    print("  The buggy version only stops due to the limit parameter!")

check_progress()

Step 7: Use Python's Debugging Tools

For complex cases, use Python's built-in debugger:

import pdb

def complex_recursive_function(n):
    """Example of using pdb for debugging"""
    if n <= 0:
        return 0

    # Set breakpoint here
    # pdb.set_trace()  # Uncomment to debug interactively

    result = n + complex_recursive_function(n - 1)
    return result

# When you uncomment pdb.set_trace(), you can:
# - Type 'n' to step to next line
# - Type 's' to step into function call
# - Type 'c' to continue execution
# - Type 'p variable_name' to print variable value
# - Type 'l' to see current location in code
# - Type 'bt' to see full call stack

print("=== PDB DEBUGGING TIPS ===\n")
print("Useful pdb commands:")
print("  n (next)      - Execute current line, move to next")
print("  s (step)      - Step into function call")
print("  c (continue)  - Continue until next breakpoint")
print("  p var         - Print value of variable")
print("  l (list)      - Show current code location")
print("  bt (backtrace)- Show full call stack")
print("  q (quit)      - Exit debugger")
print()
print("For recursive functions:")
print("  Use 'bt' to see the full recursion stack")
print("  Use 'p locals()' to see all local variables")
print("  Use 'up' and 'down' to navigate the call stack")

Complete Debugging Workflow Summary

When your recursive function fails:

Read the error completely
Error type and message
Full traceback
Line numbers
Analyze the call stack
Are parameters changing?
Is there progress toward base case?
How deep is the recursion?
Add strategic prints
Function entry (parameters)
Base case detection
Recursive calls
Return values
Manual trace
Start with smallest input
Execute by hand
Verify each step
Verify base cases
Test with n=0, empty list, etc.
Check return values
Test edge cases
Check progress
Parameters should get "smaller"
Must eventually reach base case
No cycles
Use debugging tools
pdb for interactive debugging
Recursion depth tracking
Performance profiling

Most common fixes: - Add missing base case - Fix base case return value - Correct the direction of progress (n-1 not n+1) - Add cycle detection for graphs - Convert to iteration for deep recursion - Add memoization for overlapping subproblems

Using sys.setrecursionlimit() Wisely

Python's default recursion limit is 1000 calls. Sometimes you need to increase it, but this must be done carefully.

Understanding the Recursion Limit

The recursion limit exists to prevent stack overflow—a catastrophic error that can crash Python entirely.

What happens without a limit:

import sys

def infinite_recursion(n):
    """Demonstrate why we need a recursion limit"""
    return infinite_recursion(n + 1)

print(f"Current recursion limit: {sys.getrecursionlimit()}")
print("\nWithout the limit, this would crash Python with a segmentation fault.")
print("The limit protects us by raising RecursionError instead.\n")

try:
    infinite_recursion(0)
except RecursionError as e:
    print(f"RecursionError caught at depth ~{sys.getrecursionlimit()}")
    print("This is a GOOD thing - it prevented a crash!")

When to Increase the Limit

Valid reasons: 1. You have a legitimately deep recursive structure (e.g., deep directory tree) 2. You've measured the actual depth needed 3. The depth is reasonable (< 10,000) 4. You can't easily convert to iteration

Invalid reasons: 1. Your function has infinite recursion (fix the bug instead!) 2. You don't know how deep it will go 3. You're just trying to make the error go away

How to Increase Safely

import sys

def safe_recursion_limit_increase(required_depth):
    """
    Safely increase recursion limit with validation.

    Args:
        required_depth: Maximum recursion depth needed

    Returns:
        Context manager that restores original limit
    """
    from contextlib import contextmanager

    @contextmanager
    def recursion_limit(limit):
        old_limit = sys.getrecursionlimit()

        # Validate the requested limit
        if limit > 100000:
            raise ValueError(
                f"Requested limit {limit} is dangerously high. "
                f"Consider using iteration instead."
            )

        if limit < old_limit:
            # Don't decrease the limit
            yield old_limit
            return

        try:
            # Add safety margin
            safe_limit = limit + 100
            sys.setrecursionlimit(safe_limit)
            print(f"Temporarily increased recursion limit to {safe_limit}")
            yield safe_limit
        finally:
            sys.setrecursionlimit(old_limit)
            print(f"Restored recursion limit to {old_limit}")

    return recursion_limit(required_depth)

# Example usage
def deep_recursion(n):
    """Function that needs deep recursion"""
    if n <= 0:
        return 0
    return 1 + deep_recursion(n - 1)

print("=== SAFE RECURSION LIMIT USAGE ===\n")

# Test 1: Within default limit
print("Test 1: Depth 500 (within default limit)")
result = deep_recursion(500)
print(f"Result: {result}\n")

# Test 2: Exceeds default limit
print("Test 2: Depth 1500 (exceeds default limit)")
with safe_recursion_limit_increase(1500):
    result = deep_recursion(1500)
    print(f"Result: {result}")
print()

# Test 3: Limit is restored
print("Test 3: Verify limit is restored")
print(f"Current limit: {sys.getrecursionlimit()}")

Measuring Required Depth

Before increasing the limit, measure how deep you actually need:

import sys

class DepthTracker:
    """Track maximum recursion depth"""
    def __init__(self):
        self.max_depth = 0
        self.current_depth = 0

    def enter(self):
        self.current_depth += 1
        self.max_depth = max(self.max_depth, self.current_depth)

    def exit(self):
        self.current_depth -= 1

    def reset(self):
        self.max_depth = 0
        self.current_depth = 0

def measure_recursion_depth(func, *args, **kwargs):
    """
    Measure the maximum recursion depth of a function call.

    Args:
        func: Function to measure
        *args, **kwargs: Arguments to pass to function

    Returns:
        tuple: (result, max_depth)
    """
    tracker = DepthTracker()

    # Wrap the function to track depth
    original_func = func

    def wrapped(*args, **kwargs):
        tracker.enter()
        try:
            return original_func(*args, **kwargs)
        finally:
            tracker.exit()

    # Replace recursive calls with wrapped version
    # (This is a simplified example - real implementation would need more work)
    result = wrapped(*args, **kwargs)

    return result, tracker.max_depth

# Example: Measure depth for different inputs
def factorial(n, tracker=None):
    """Factorial with depth tracking"""
    if tracker:
        tracker.enter()

    try:
        if n <= 1:
            return 1
        return n * factorial(n - 1, tracker)
    finally:
        if tracker:
            tracker.exit()

print("=== MEASURING RECURSION DEPTH ===\n")

test_cases = [10, 50, 100, 500, 1000]

for n in test_cases:
    tracker = DepthTracker()
    result = factorial(n, tracker)

    print(f"factorial({n}):")
    print(f"  Max depth: {tracker.max_depth}")
    print(f"  Current limit: {sys.getrecursionlimit()}")

    if tracker.max_depth > sys.getrecursionlimit() * 0.8:
        print(f"  ⚠ WARNING: Approaching recursion limit!")

    print()

Platform-Specific Considerations

Different platforms have different stack sizes:

import sys
import platform

def check_platform_limits():
    """Check platform-specific recursion characteristics"""
    print("=== PLATFORM RECURSION LIMITS ===\n")

    print(f"Platform: {platform.system()} {platform.machine()}")
    print(f"Python version: {sys.version}")
    print(f"Default recursion limit: {sys.getrecursionlimit()}")
    print()

    # Test actual stack depth
    def test_depth(n):
        if n <= 0:
            return n
        return test_depth(n - 1)

    # Find maximum safe depth
    print("Testing maximum safe depth...")

    for limit in [1000, 2000, 5000, 10000, 20000]:
        sys.setrecursionlimit(limit)
        try:
            test_depth(limit - 100)
            print(f"  Limit {limit}: ✓ Safe")
        except RecursionError:
            print(f"  Limit {limit}: ✗ Too high")
            break

    # Restore default
    sys.setrecursionlimit(1000)

    print()
    print("Recommendations:")
    print("  - Linux/Mac: Usually safe up to 10,000")
    print("  - Windows: Usually safe up to 5,000")
    print("  - Always test on target platform")
    print("  - Consider iteration for depths > 10,000")

check_platform_limits()

Best Practices Summary

DO:

✓ Measure actual depth needed before increasing limit ✓ Add safety margin (e.g., required_depth + 100) ✓ Use context manager to restore original limit ✓ Document why you're increasing the limit ✓ Test on target platform ✓ Consider iteration for very deep recursion

DON'T:

✗ Increase limit to "fix" infinite recursion bugs ✗ Set limit arbitrarily high without measuring ✗ Forget to restore original limit ✗ Exceed 10,000 without strong justification ✗ Use recursion when iteration is clearer

Decision Framework

Should you increase the recursion limit?

Is the recursion infinite due to a bug?
  YES → Fix the bug, don't increase limit
  NO  ↓

Is the required depth > 10,000?
  YES → Use iteration instead
  NO  ↓

Can you easily convert to iteration?
  YES → Consider iteration (safer)
  NO  ↓

Have you measured the actual depth needed?
  NO  → Measure first, then decide
  YES ↓

Is the depth reasonable for your platform?
  YES → Increase limit with safety margin
  NO  → Use iteration or divide-and-conquer

Example: Production-Ready Approach

import sys
from contextlib import contextmanager

@contextmanager
def temporary_recursion_limit(limit):
    """
    Context manager for temporarily increasing recursion limit.

    Args:
        limit: Required recursion depth

    Raises:
        ValueError: If limit is unreasonably high
    """
    if limit > 50000:
        raise ValueError(
            f"Recursion limit {limit} is too high. "
            f"Consider using an iterative approach instead."
        )

    old_limit = sys.getrecursionlimit()

    if limit <= old_limit:
        # No need to increase
        yield old_limit
        return

    try:
        # Add 10% safety margin
        safe_limit = int(limit * 1.1)
        sys.setrecursionlimit(safe_limit)
        yield safe_limit
    finally:
        sys.setrecursionlimit(old_limit)

def process_deep_structure(data, max_depth=None):
    """
    Process a potentially deep recursive structure.

    Args:
        data: Data to process
        max_depth: Known maximum depth (if available)
    """
    if max_depth and max_depth > 1000:
        # Need to increase limit
        with temporary_recursion_limit(max_depth):
            return _process_recursive(data)
    else:
        # Within default limit
        return _process_recursive(data)

def _process_recursive(data):
    """Internal recursive implementation"""
    # ... recursive logic here ...
    pass

# Usage example
print("=== PRODUCTION-READY PATTERN ===\n")
print("This pattern:")
print("  ✓ Measures depth when possible")
print("  ✓ Only increases limit when necessary")
print("  ✓ Adds safety margin")
print("  ✓ Validates limit is reasonable")
print("  ✓ Automatically restores original limit")
print("  ✓ Provides clear error messages")

Lab: Debug 5 Broken Recursive Functions

Now it's time to apply everything you've learned. Below are five broken recursive functions. Your task is to:

Identify the bug using the diagnostic techniques from this chapter
Explain why it fails with reference to the failure mode
Fix the bug and verify the fix works
Add appropriate error handling if needed

For each function, follow the systematic debugging workflow: - Read the error completely - Trace the call stack - Add strategic prints - Manually trace with small input - Verify base cases - Check progress toward base case

Bug 1: The Missing Base Case

def sum_digits(n):
    """
    Sum the digits of a positive integer.

    Example: sum_digits(123) should return 6 (1 + 2 + 3)

    BUG: This function has a critical error!
    """
    digit = n % 10
    rest = n // 10
    return digit + sum_digits(rest)

# Test cases
print("=== BUG 1: Missing Base Case ===\n")
print("Testing sum_digits(123)...")

try:
    result = sum_digits(123)
    print(f"Result: {result}")
except RecursionError as e:
    print(f"RecursionError: {e}")
    print("\nDiagnostic questions:")
    print("1. What happens when n becomes 0?")
    print("2. Is there a base case to stop the recursion?")
    print("3. What should sum_digits(0) return?")

Your task: 1. Run the code and observe the error 2. Add print statements to see what's happening 3. Identify the missing base case 4. Fix the function 5. Verify it works with test cases: 0, 5, 123, 9999

Hint: What should happen when there are no more digits to sum?

Bug 2: The Wrong Base Case Value

def product_of_list(lst):
    """
    Calculate the product of all numbers in a list.

    Example: product_of_list([2, 3, 4]) should return 24

    BUG: Returns wrong result!
    """
    if len(lst) == 0:
        return 0  # Base case

    first = lst[0]
    rest = lst[1:]
    return first * product_of_list(rest)

# Test cases
print("\n=== BUG 2: Wrong Base Case Value ===\n")

test_cases = [
    ([2, 3, 4], 24),
    ([5], 5),
    ([1, 2, 3, 4, 5], 120),
    ([], 1),  # Edge case: empty list
]

for lst, expected in test_cases:
    result = product_of_list(lst)
    status = "✓" if result == expected else "✗"
    print(f"{status} product_of_list({lst}) = {result} (expected {expected})")

print("\nDiagnostic questions:")
print("1. What is the identity value for multiplication?")
print("2. What should product_of_list([]) return?")
print("3. Why does [5] return 0 instead of 5?")

Your task: 1. Observe that all results are 0 2. Manually trace product_of_list([2, 3]) 3. Identify why the base case value is wrong 4. Fix the base case 5. Verify all test cases pass

Hint: What is the identity element for multiplication? (What can you multiply by without changing the result?)

Bug 3: The Wrong Direction

def find_max(lst):
    """
    Find the maximum value in a list.

    Example: find_max([3, 1, 4, 1, 5]) should return 5

    BUG: Infinite recursion!
    """
    if len(lst) == 1:
        return lst[0]

    # Compare first element with max of rest
    first = lst[0]
    rest_max = find_max(lst)  # BUG: Wrong slice!

    return first if first > rest_max else rest_max

# Test case
print("\n=== BUG 3: Wrong Direction ===\n")
print("Testing find_max([3, 1, 4, 1, 5])...")

try:
    result = find_max([3, 1, 4, 1, 5])
    print(f"Result: {result}")
except RecursionError as e:
    print(f"RecursionError: maximum recursion depth exceeded")
    print("\nDiagnostic questions:")
    print("1. Is the list getting smaller with each recursive call?")
    print("2. What should 'rest' be?")
    print("3. Add a print to see what's being passed to the recursive call")

Your task: 1. Add print statements to show the list at each call 2. Observe that the list never changes 3. Identify the incorrect slice 4. Fix the recursive call 5. Verify it finds the maximum correctly

Hint: The recursive call should be on a smaller portion of the list.

Bug 4: The Mutable Default Argument

def collect_leaves(tree, leaves=[]):
    """
    Collect all leaf values from a binary tree.

    Tree format: [value, left_subtree, right_subtree]
    Leaf: [value, None, None]

    Example:
        tree = [1, [2, None, None], [3, None, None]]
        Should return [2, 3]

    BUG: Results accumulate across calls!
    """
    if tree is None:
        return leaves

    value, left, right = tree

    # If it's a leaf, add to collection
    if left is None and right is None:
        leaves.append(value)
        return leaves

    # Recurse on children
    if left:
        collect_leaves(left, leaves)
    if right:
        collect_leaves(right, leaves)

    return leaves

# Test cases
print("\n=== BUG 4: Mutable Default Argument ===\n")

tree1 = [1, [2, None, None], [3, None, None]]
tree2 = [10, [20, None, None], [30, None, None]]

print("First call:")
result1 = collect_leaves(tree1)
print(f"  collect_leaves(tree1) = {result1}")
print(f"  Expected: [2, 3]")

print("\nSecond call:")
result2 = collect_leaves(tree2)
print(f"  collect_leaves(tree2) = {result2}")
print(f"  Expected: [20, 30]")
print(f"  Actual: {result2} ← BUG: Contains values from first call!")

print("\nDiagnostic questions:")
print("1. Why does the second call include values from the first call?")
print("2. When is the default argument [] created?")
print("3. Is the same list object reused across calls?")

Your task: 1. Observe that results accumulate across calls 2. Add print(id(leaves)) to see if it's the same object 3. Understand why mutable defaults are dangerous 4. Fix by using None as default 5. Verify each call returns independent results

Hint: Default arguments are evaluated once at function definition, not at each call.

Bug 5: The Performance Bug

import time

def count_paths(grid, row, col):
    """
    Count paths from (0,0) to (row, col) in a grid.
    Can only move right or down.

    Example: count_paths(2, 2) should return 6

    BUG: Extremely slow for large inputs!
    """
    # Base cases
    if row == 0 or col == 0:
        return 1  # Only one path along edge

    # Recursive case: paths from above + paths from left
    paths_from_above = count_paths(grid, row - 1, col)
    paths_from_left = count_paths(grid, row, col - 1)

    return paths_from_above + paths_from_left

# Test cases
print("\n=== BUG 5: Performance Bug ===\n")

test_cases = [
    (2, 2),
    (5, 5),
    (10, 10),
    (15, 15),  # This will be very slow!
]

for row, col in test_cases:
    start = time.time()
    result = count_paths(None, row, col)
    elapsed = time.time() - start

    print(f"count_paths({row}, {col}) = {result}")
    print(f"  Time: {elapsed:.4f} seconds")

    if elapsed > 1.0:
        print(f"  ⚠ WARNING: Too slow!")
        print(f"  This is an exponential time algorithm.")
        print(f"  Hint: Are we computing the same values multiple times?")
        break

print("\nDiagnostic questions:")
print("1. How many times is count_paths(5, 5) called when computing count_paths(10, 10)?")
print("2. Are there overlapping subproblems?")
print("3. What technique can we use to avoid recomputation?")

Your task: 1. Observe the exponential slowdown 2. Add a call counter to see how many times each (row, col) is computed 3. Identify the overlapping subproblems 4. Add memoization to cache results 5. Measure the performance improvement

Hint: Use a dictionary to cache results for each (row, col) pair.

Solutions and Explanations

After attempting all five bugs, compare your solutions with the corrected versions below:

Bug 1 Solution: Add Base Case

def sum_digits_fixed(n):
    """Fixed version with proper base case"""
    # Base case: no more digits
    if n == 0:
        return 0

    digit = n % 10
    rest = n // 10
    return digit + sum_digits_fixed(rest)

# Verify
print("\n=== BUG 1 SOLUTION ===\n")
test_cases = [0, 5, 123, 9999]
for n in test_cases:
    result = sum_digits_fixed(n)
    print(f"sum_digits({n}) = {result}")

Explanation: The base case if n == 0: return 0 stops the recursion when there are no more digits. Without it, the function recurses forever.

Bug 2 Solution: Fix Base Case Value

def product_of_list_fixed(lst):
    """Fixed version with correct base case value"""
    if len(lst) == 0:
        return 1  # Identity for multiplication

    first = lst[0]
    rest = lst[1:]
    return first * product_of_list_fixed(rest)

# Verify
print("\n=== BUG 2 SOLUTION ===\n")
test_cases = [
    ([2, 3, 4], 24),
    ([5], 5),
    ([1, 2, 3, 4, 5], 120),
    ([], 1),
]

for lst, expected in test_cases:
    result = product_of_list_fixed(lst)
    status = "✓" if result == expected else "✗"
    print(f"{status} product_of_list({lst}) = {result}")

Explanation: The identity element for multiplication is 1 (not 0). Multiplying by 1 doesn't change the result, so product([]) = 1 is correct.

Bug 3 Solution: Fix Recursive Call

def find_max_fixed(lst):
    """Fixed version with correct slice"""
    if len(lst) == 1:
        return lst[0]

    first = lst[0]
    rest_max = find_max_fixed(lst[1:])  # Fixed: lst[1:] not lst

    return first if first > rest_max else rest_max

# Verify
print("\n=== BUG 3 SOLUTION ===\n")
test_cases = [
    [3, 1, 4, 1, 5],
    [10],
    [5, 5, 5, 5],
    [-1, -5, -3, -2],
]

for lst in test_cases:
    result = find_max_fixed(lst)
    print(f"find_max({lst}) = {result}")

Explanation: The recursive call must be on lst[1:] (all elements except the first), not lst (the entire list). Without this, the list never gets smaller.

Bug 4 Solution: Fix Mutable Default

def collect_leaves_fixed(tree, leaves=None):
    """Fixed version with None default"""
    if leaves is None:
        leaves = []  # Create new list for each top-level call

    if tree is None:
        return leaves

    value, left, right = tree

    if left is None and right is None:
        leaves.append(value)
        return leaves

    if left:
        collect_leaves_fixed(left, leaves)
    if right:
        collect_leaves_fixed(right, leaves)

    return leaves

# Verify
print("\n=== BUG 4 SOLUTION ===\n")

tree1 = [1, [2, None, None], [3, None, None]]
tree2 = [10, [20, None, None], [30, None, None]]

result1 = collect_leaves_fixed(tree1)
print(f"collect_leaves(tree1) = {result1}")

result2 = collect_leaves_fixed(tree2)
print(f"collect_leaves(tree2) = {result2}")

print(f"\nIndependent results: {result1 is not result2}")

Explanation: Using None as the default and creating a new list inside the function ensures each call gets its own independent list.

Bug 5 Solution: Add Memoization

import time

def count_paths_fixed(grid, row, col, memo=None):
    """Fixed version with memoization"""
    if memo is None:
        memo = {}

    # Check cache
    if (row, col) in memo:
        return memo[(row, col)]

    # Base cases
    if row == 0 or col == 0:
        return 1

    # Recursive case with caching
    paths_from_above = count_paths_fixed(grid, row - 1, col, memo)
    paths_from_left = count_paths_fixed(grid, row, col - 1, memo)

    result = paths_from_above + paths_from_left
    memo[(row, col)] = result  # Cache the result

    return result

# Compare performance
print("\n=== BUG 5 SOLUTION ===\n")

test_cases = [(5, 5), (10, 10), (15, 15), (20, 20)]

print("Without memoization:")
for row, col in test_cases[:2]:  # Only test small cases
    start = time.time()
    result = count_paths(None, row, col)
    elapsed = time.time() - start
    print(f"  count_paths({row}, {col}) = {result} in {elapsed:.4f}s")

print("\nWith memoization:")
for row, col in test_cases:
    start = time.time()
    result = count_paths_fixed(None, row, col)
    elapsed = time.time() - start
    print(f"  count_paths({row}, {col}) = {result} in {elapsed:.6f}s")

Explanation: Memoization caches results for each (row, col) pair, avoiding redundant computation. This reduces time complexity from O(2^n) to O(n*m).

Lab Summary

What you practiced: 1. ✓ Reading error messages and tracebacks 2. ✓ Adding diagnostic print statements 3. ✓ Manual tracing with small inputs 4. ✓ Identifying missing or incorrect base cases 5. ✓ Detecting wrong direction in recursion 6. ✓ Understanding mutable default arguments 7. ✓ Recognizing performance issues from overlapping subproblems 8. ✓ Applying memoization to optimize recursive functions

Key takeaways: - Most recursive bugs fall into a few common patterns - Systematic debugging is more effective than random fixes - Base cases are the most common source of errors - Mutable defaults cause subtle bugs that persist across calls - Performance issues often indicate overlapping subproblems - Memoization can transform exponential algorithms into polynomial ones

Chapter Summary

The Journey: From Mysterious Failures to Systematic Debugging

We started with a simple directory size calculator and progressively exposed its failure modes:

Iteration	Failure Mode	Diagnostic Technique	Solution
0	None	Basic implementation	Working but fragile
1	Permission denied	Error message analysis	Add try-except blocks
2	Infinite recursion (cycles)	Call stack visualization	Add visited set
3	Stack overflow (deep trees)	Depth tracking	Increase limit or use iteration

Key Debugging Techniques Learned

1. Strategic Print Statements

Show function entry/exit with indentation
Display parameters and return values
Visualize the recursion tree
Track progress toward base case

2. Call Stack Analysis

Read tracebacks completely
Identify repeated patterns (cycles)
Measure recursion depth
Detect wrong direction

3. Manual Tracing

Execute by hand with small inputs
Verify base cases
Check combination logic
Understand the recursion pattern

4. Depth Tracking

Measure actual vs. expected depth
Detect approaching recursion limit
Decide between recursion and iteration
Set appropriate limits

5. Performance Profiling

Count function calls
Identify overlapping subproblems
Measure time complexity
Apply memoization when needed

Common Failure Modes Reference

Quick diagnostic guide:

RecursionError + same line repeated
  → Infinite recursion (missing/unreachable base case)

RecursionError + parameters changing
  → Legitimate deep recursion (increase limit or use iteration)

Wrong result + no error
  → Incorrect base case value or combination logic

Results accumulate across calls
  → Mutable default argument

Exponential slowdown
  → Overlapping subproblems (add memoization)

Permission/IO errors
  → Missing error handling

The Systematic Debugging Workflow

When your recursive function fails:

Read the error completely - Extract all information from the message and traceback
Analyze the call stack - Understand the sequence and depth of calls
Add strategic prints - Make the invisible visible
Manual trace - Execute by hand with smallest input
Verify base cases - Test with n=0, empty list, etc.
Check progress - Ensure parameters move toward base case
Use debugging tools - pdb, depth tracking, profiling

Using sys.setrecursionlimit() Wisely

Decision framework: - Measure actual depth needed - Only increase if depth < 10,000 - Add safety margin (10-20%) - Use context manager to restore limit - Consider iteration for very deep recursion - Never increase to "fix" infinite recursion bugs

Production-Ready Patterns

For robust recursive code: - Always handle I/O errors gracefully - Add cycle detection for graph traversal - Track recursion depth for monitoring - Use memoization for overlapping subproblems - Provide iterative alternative for deep recursion - Document recursion depth requirements - Test with edge cases (empty, single element, deep structures)

What Makes a Good Recursive Function?

Checklist: - [ ] Clear, reachable base case(s) - [ ] Recursive calls make progress toward base case - [ ] Correct base case return values - [ ] Proper error handling for I/O operations - [ ] Cycle detection for graph structures - [ ] Memoization for overlapping subproblems (if applicable) - [ ] Appropriate recursion depth for the problem - [ ] Clear documentation of assumptions and limits

Final Thoughts

Debugging recursive code is a skill that improves with practice. The key is to:

Make the invisible visible - Use prints, traces, and visualization
Think systematically - Follow a structured debugging process
Understand the patterns - Recognize common failure modes
Test thoroughly - Edge cases reveal bugs
Know when to iterate - Recursion isn't always the answer

The techniques in this chapter apply to all recursive code, from simple list processing to complex tree algorithms. Master these debugging skills, and recursion will become a powerful, reliable tool in your programming arsenal.

Remember: Every expert debugger was once a beginner who learned to read error messages carefully, trace execution systematically, and think through the recursive logic step by step. You now have the tools to do the same.